package com.zhengb.algorithmdemo.leetcode.tree;

import java.util.LinkedList;
import java.util.List;

/**
 * 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
 * <p>
 * 调用 next() 将返回二叉搜索树中的下一个最小的数。
 * https://leetcode-cn.com/problems/binary-search-tree-iterator/
 *
 * @author zhengbo
 * @date 2020/4/14
 */
public class BstIterator {

    private List<Integer> treeSortList = new LinkedList<>();

    private int curIndex = 0;

    private void inOrderTraverseTree(TreeNode root, List<Integer> list) {

        if (root != null) {
            inOrderTraverseTree(root.left, list);
            list.add(root.val);
            inOrderTraverseTree(root.right, list);
        }
    }

    public BstIterator(TreeNode root) {
        inOrderTraverseTree(root, treeSortList);
    }

    /**
     * @return the next smallest number
     */
    public int next() {
        int value = treeSortList.get(curIndex);
        curIndex++;

        return value;
    }

    /**
     * @return whether we have a next smallest number
     */
    public boolean hasNext() {

        return curIndex != treeSortList.size();
    }

    public static void main(String[] args) {

        TreeNode seven = new TreeNode(7);
        TreeNode three = new TreeNode(3);
        TreeNode fifteen = new TreeNode(15);
        TreeNode nine = new TreeNode(9);
        TreeNode twenty = new TreeNode(20);

        seven.left = three;
        seven.right = fifteen;

        fifteen.left = nine;
        fifteen.right = twenty;

        BstIterator iterator = new BstIterator(seven);

        System.out.println(iterator.treeSortList);

        System.out.println(iterator.next()); // 返回 3
        System.out.println(iterator.next());    // 返回 7
        System.out.println(iterator.hasNext()); // 返回 true
        System.out.println(iterator.next());// 返回 9
        System.out.println(iterator.hasNext());// 返回 true
        System.out.println(iterator.next());// 返回 15
        System.out.println(iterator.hasNext());// 返回 true
        System.out.println(iterator.next());// 返回 20
        System.out.println(iterator.hasNext());// 返回 false

    }
}
